/**
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

 

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
*/

class Solution {
    List<List<Integer>> res=new ArrayList();
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        boolean[] visited=new boolean[nums.length];
        dfs(0,0, target,nums,new ArrayList<Integer>(),visited);
        return res;
    }
    public void dfs(int n,int sum,int target,int[] nums,List<Integer> path,boolean[] visited){
        if(path.size()==4){
            if(sum==target){
                res.add(new ArrayList(path));
            }
            return;
        }
        for(int i=n;i<nums.length;i++){
            if(i>n && !visited[i] && nums[i]==nums[i-1]){
                continue;
            }
            visited[i]=true;
            path.add(nums[i]);
            sum=sum+nums[i];
            dfs(i+1,sum,target,nums,path,visited);
            path.remove(path.size()-1);
            sum=sum-nums[i];
            visited[i]=false;
        }
        
    }
}